import java.net.InetAddress;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-04-24
 * Time: 10:01
 */
public class Test4 {
    //-------------------------------------------Day31-----------------------------------------------

    // No.1:美国节日
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int year = scanner.nextInt();
            int subYear = year - 1900;
            int dayLen = 0;
            for (int i = 1900; i < subYear + 1900; i++) {
                if (isLeapYear(i)) {
                    dayLen += 366;
                } else {
                    dayLen += 365;
                }
            }
            // 以上循环计算1900-1-1到year-1-1之间的天数,也可以理解为year-1-1这一天

            // 元旦
            System.out.println(year + "-01-01");
            // 马丁路德金纪念日
            int count = 0;
            int tmpLen = dayLen;
            for (int i = 2; i <= 31; i++) {
                tmpLen += 1;
                if ((tmpLen % 7 + 1) == 1) {
                    count++;
                }
                if (count == 3) {
                    System.out.printf("%d-01-%02d\n", year, i);
                    break;
                }
            }

            // 总统节
            dayLen += 30;// 对于1月最后一天
            tmpLen = dayLen;
            count = 0;
            int day = 0;
            if (isLeapYear(year)) {
                day = 29;
            } else {
                day = 28;
            }
            for (int i = 1; i <= day; i++) {
                tmpLen += 1;
                if ((tmpLen % 7 + 1) == 1) {
                    count++;
                }
                if (count == 3) {
                    System.out.printf("%d-02-%02d\n", year, i);
                    break;
                }
            }
            // 阵亡将士纪念日
            dayLen += day + 31 + 30;
            tmpLen = dayLen + 31;
            for (int i = 31; i >= 1; i--) {
                if ((tmpLen % 7 + 1) == 1) {
                    System.out.printf("%d-05-%02d\n", year, i);
                    break;
                }
                tmpLen--;
            }
            // 美国国庆
            System.out.println(year + "-07-04");
            // 劳动节
            dayLen += 31 + 30 + 31 + 31;
            tmpLen = dayLen;
            for (int i = 1; i <= dayLen; i++) {
                tmpLen++;
                if ((tmpLen % 7 + 1) == 1) {
                    System.out.printf("%d-09-%02d\n", year, i);
                    break;
                }
            }
            // 感恩节
            dayLen += 30 + 31;
            tmpLen = dayLen;
            count = 0;
            for (int i = 1; i <= tmpLen; i++) {
                tmpLen++;
                if ((tmpLen % 7 + 1) == 4) {
                    count++;
                }
                if (count == 4) {
                    System.out.printf("%d-11-%02d\n", year, i);
                    break;
                }
            }

            // 圣诞节
            System.out.println(year + "-12-25");
            System.out.println();
        }

    }

//    private static boolean isLeapYear(int year) {
//        if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {
//            return true;
//        }
//        return false;
//    }


    // 分解因数
    public static boolean isPerm(int n) {
        // 判断是否为素数
        if (n == 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            System.out.print(n + " =");

            // 递归打印
            findFac(n);
            // 每次更新计数次数
            count = 0;
            System.out.println();
        }

    }

    // 计数器
    public static int count = 0;

    // 递归函数
    public static void findFac(int n) {
        if (isPerm(n)) {
            // 如果是素数，直接打印
            System.out.print(" " + n);
        } else {
            for (int i = 2; i <= (int) Math.sqrt(n); i++) {
                // i是素数，并且能被整除
                if (isPerm(i) && n % i == 0) {
                    if (count == 0) {
                        System.out.print(" " + i);
                    } else {
                        System.out.print(" * " + i);
                    }
                    count++;

                    if (isPerm(n / i)) {
                        System.out.print(" * " + n / i);
                    } else {
                        findFac(n / i);
                    }
                    break;
                }
            }
        }

    }


    //-------------------------------------------Day32-----------------------------------------------


    // No.1:淘宝网店
    private static boolean isLeapYear(int year) {
        if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {
            return true;
        }
        return false;
    }

    private static boolean isFacMonth(int month) {
        if (month == 2 || month == 3 || month == 5 || month == 7 || month == 11) {
            return true;
        } else {
            return false;
        }

    }

    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入
        while (scanner.hasNextInt()) {
            int year1 = scanner.nextInt();
            int month1 = scanner.nextInt();
            int day1 = scanner.nextInt();

            int year2 = scanner.nextInt();
            int month2 = scanner.nextInt();
            int day2 = scanner.nextInt();
            // 计算纯年份收入
            int someTotal = 0;
            int[] array = {0, 31 * 2, 0, 31, 30 * 2, 31, 30 * 2, 31, 31 * 2, 30 * 2, 31 * 2, 30, 31 * 2};
            int sumYear1 = 0;
            int sumYear2 = 0;

            if (year2 - year1 >= 1) {
                int t = year2 - year1 - 1;
                someTotal = (31 * 2 + 31 + 30 * 2 + 31 + 30 * 2 + 31 + 31 * 2 + 30 * 2 + 31 * 2 + 30 + 31 * 2) * t;

                sumYear1 = 0;
                sumYear2 = 0;

                for (int i = year1 + 1; i < year2; i++) {
                    // 二月天数
                    int month2Day = 0;
                    if (isLeapYear(i)) {
                        month2Day = 29;
                    } else {
                        month2Day = 28;
                    }
                    someTotal += (month2Day);
                }


                // 计算year1和year2年份收入
                if (isLeapYear(year1)) {
                    array[2] = 29;
                } else {
                    array[2] = 28;
                }
                for (int i = month1 + 1; i <= 12; i++) {
                    sumYear1 += array[i];
                }
                if (isFacMonth(month1)) {
                    sumYear1 += array[month1] - day1 + 1;
                } else {
                    sumYear1 += array[month1] - (day1) * 2 + 2;
                }


                if (isLeapYear(year2)) {
                    array[2] = 29;
                } else {
                    array[2] = 28;
                }
                for (int i = 1; i <= month2 - 1; i++) {
                    sumYear2 += array[i];
                }
                if (isFacMonth(month2)) {
                    sumYear2 += (day2);
                } else {
                    sumYear2 += (day2) * 2;
                }


            } else {
                for (int i = month1 + 1; i <= month2 - 1; i++) {
                    someTotal += array[i];
                }
                if (month1 != month2) {
                    if (isFacMonth(month1)) {
                        someTotal += array[month1] - day1 + 1;
                    } else {
                        someTotal += array[month1] - (day1) * 2 + 2;
                    }
                    if (isFacMonth(month2)) {
                        someTotal += day2;
                    } else {
                        someTotal += (day2) * 2;
                    }
                } else {
                    if (isFacMonth(month1)) {
                        someTotal += (day2 - day1) + 1;
                    } else {
                        someTotal += (day2 - day1 + 1) * 2;
                    }
                }
            }

            System.out.println(sumYear1 + sumYear2 + someTotal);


        }

    }

    // No.4:斐波那契凤尾
    public static void main4(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] array = new int[100001];
        //构造 1-1000000 之间的斐波那契数组
        array[1] = 1;
        array[2] = 2;
        for (int i = 3; i < 100001; i++) {
            array[i] = (array[i - 1] + array[i - 2]) % 1000000;
        }
        int n = scanner.nextInt();
        System.out.println(array[n]);

    }

    //-------------------------------------------Day33-----------------------------------------------
    //No.1:减花布条
    public static void main5(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String s = scanner.next();
            String t = scanner.next();
            // 特殊情况
            if (t.length() > s.length()) {
                System.out.println(0);
                return;
            }
            int count = 0;
            // 一般情况
            int i =0;
            int j = 0;

            while (i<s.length()) {
                char ch_t = t.charAt(j);
                char ch_s = s.charAt(i);
                int tmp = i;
                if (ch_s==ch_t) {
                    while (i < s.length() && j < t.length() && ch_s == ch_t) {
                        i++;
                        j++;
                        if (i < s.length() && j < t.length()) {
                            ch_s = s.charAt(i);
                            ch_t = t.charAt(j);
                        }
                    }
                    if (j==t.length()) {
                        count++;
                    } else {
                        i=tmp+1;
                    }

                    j=0;
                } else {
                    i++;
                    j=0;
                }
            }
            System.out.println(count);
        }
    }

    //No.2:客似云来
    public static void main6(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 构造 1-80 之间的斐波那契数
        long[] array = new long[81];
        array[1] = 1;
        array[2] = 1;
        for (int i = 3; i <=80 ; i++) {
            array[i] = array[i-1]+array[i-2];
        }
        while (scanner.hasNextInt()) {
            int n1 = scanner.nextInt();
            int n2 = scanner.nextInt();
            long sum = 0;
            for (int i = n1; i <= n2; i++) {
                sum+=array[i];
            }
            System.out.println(sum);
        }

    }

    //-------------------------------------------Day34-----------------------------------------------
    // No.1:养兔子
    public static void main7(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLong()) {
            // 这里需要使用长整型，因为测试用例比较大
            long fib1 = 1;
            long fib2 = 2;
            int N = scanner.nextInt();
            if (N<=2) {
                System.out.println(N);
                continue;
            }
            while (N>2) {
                long tmp = fib1;
                fib1 = fib2;
                fib2 = tmp+fib2;
                N--;
            }
            System.out.println(fib2);
        }
    }

    // No2:邮件多客户
    public static void main8(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            // 输入
            int n = scanner.nextInt();
            // 吃空白符
            scanner.nextLine();
            String[] names = new String[n];
            for (int i = 0; i < n; i++) {
                String name = scanner.nextLine();
                if (name.contains(",")|| name.contains(" ")) {
                    StringBuilder sb = new StringBuilder(name);
                    sb.insert(0,'"');
                    sb.append('"');
                    name = sb.toString();
                }
                names[i] = name;
            }
            for (int i = 0; i < n-1; i++) {
                System.out.print(names[i]+", ");
            }
            System.out.println(names[n-1]);
        }
    }

    //-------------------------------------------Day35-----------------------------------------------

    // 错排算法
    public static double noPrice(int n) {
        if(n==1){
            return 0;
        }else if(n==2){
            return 1;
        }else {
            return (n-1)*(noPrice(n-1)+noPrice(n-2));
        }
    }
    // 阶乘算法
    public static double digit(int n) {
        double sum = 1.0;
        while (n>1) {
            sum *= n;
            n--;
        }
        return sum;
    }
    // No.1：年会抽奖
    public static void main9(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 多组输入
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            System.out.println(digit(n));
            System.out.println(noPrice(n));
            double result = noPrice(n)/digit(n);
            System.out.printf("%.2f%%\n",result*100);

        }
    }

    // No.2:抄送列表

//    public static void main(String[] args) {
//        // 思路：检索字符串
//        Scanner scanner = new Scanner(System.in);
//        while (scanner.hasNextLine()) {
//            String users = scanner.nextLine();
//            String destUser = scanner.nextLine();
//            // 检索函数
//            searchStr(users,destUser);
//        }
//    }

//    private static boolean searchStr(String users, String destUser) {
//        int i = 0;
//        int j = 0;
//        while (i<users.length() && j<destUser.length()) {
//            // 带引号的情况
//            if (users.charAt(i)=='"') {
//                i++;
//                while (i<users.length() && j<destUser.length() && users.charAt(i)==destUser.charAt(i)) {
//                    i++;
//                    j++;
//                }
//                if (users.charAt(i)=='"') {
//                    return true;
//                }
//            }
////            if (users.charAt(i))
//
//
//        }
//    }

    //-------------------------------------------Day36-----------------------------------------------
    // 这次我的“死”的很难看

    //-------------------------------------------Day37-----------------------------------------------


    // No.1:数据库连接池
    public static void main10(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            // 输入n个请求
            int n = sc.nextInt();
            // 使用哈希表处理(思路：找到哈希表存在的最大值)
            HashSet<String> hashSet = new HashSet<>();
            int max = 0;
            int tmp = 0;

            for (int i = 0 ;i < n;i ++) {
                String id = sc.next();
                String operate = sc.next();
                // 如果当前哈希表中没有当前 id
                if (!hashSet.contains(id)) {
                    hashSet.add(id);
                    tmp ++;
                } else {
                    hashSet.remove(id);
                    tmp--;
                }
                if (tmp >max) {
                    max = tmp;
                }
            }
            System.out.println(max);

        }

    }

    // No.2:mkdir
    public static void main11(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            // “吃空格”
            sc.nextLine();
            List<String> list = new LinkedList<>();
            // 构造字符串链表
            for (int i = 0; i < n; i++) {
                String x = sc.nextLine();
                list.add(x);

            }
            // 按字典排序
            Collections.sort(list);
            int i = 1;
            int j = 0;
            while (i< list.size()) {
                while (j<i) {
                    if (list.get(i).contains(list.get(j))) {
                        list.remove(j);
                        // i坐标“回表”
                        i=i-1;
                    } else {
                        j++;
                    }
                }
                i++;
            }
            // 打印操作
            for (i = 0; i < list.size(); i++) {
                System.out.println("mkdir -p "+list.get(i));
            }
            System.out.println();

        }

    }

    //-------------------------------------------Day38-----------------------------------------------

    // No.1:

    // No.2:蘑菇阵
//    public static int count2 = 0;
//    // mat：迷宫矩阵，row，col
//    // x,y：当前位置
//    // book：标记矩阵，标记当前位置是否走过
//    // path：保存当前路径的每一个位置
//    // minPath：保存最短路径
//    public static void getPath(int row, int col, int x, int y, int[][] book) {
//        // 判断(x,y)是否越界，是否走过，是否有障碍
//        if (x < 0 || x >= row || y < 0 || y >= col || book[x][y] == 1) {
//            return;
//        }
//        // 判断当前位置是否为出口位置
//        if (x == row - 1 && y == col - 1) {
//            // 一条新的路径产生
//            // 判断是否为更短路径
//            count2++;
//            return;
//        }
//        // 标记当前位置
//        book[x][y] = 1;
//
//        // 继续搜索(x,y)的上下左右四个方向
//        getPath(row, col, x + 1, y, book);
//        getPath(row, col, x - 1, y, book);
//        getPath(row, col, x, y - 1, book);
//        getPath(row, col, x, y + 1, book);
//
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int M = scanner.nextInt();
//        int N = scanner.nextInt();
//        int[][] array = new int[M][N];
//        getPath(M,N,0,0,array);
//        int total = count2;
//        count2 = 0;
//
//        int[][] book = new int[M][N];
//        int K = scanner.nextInt();
//        for (int i = 0; i < K; i++) {
//            int a = scanner.nextInt();
//            int b = scanner.nextInt();
//            book[a-1][b-1] = 1;
//        }
//        getPath(M,N,0,0,book);
//        System.out.printf("%.2f",(double) count2/total);
//
//    }

    //-------------------------------------------Day39-----------------------------------------------

    // 最长公共字串。题目理解错了！
    public static void main12(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            int count = 0;
            int[] array1 = new int[26];
            int[] array2 = new int[26];
            String s1 = sc.next().toLowerCase();
            String s2 = sc.next().toLowerCase();
            for (int i = 0;i<s1.length();i++) {
                array1[s1.charAt(i)-'a']++;
            }
            for (int i = 0;i<s2.length();i++) {
                array2[s2.charAt(i)-'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0;i<array1.length;i++) {
                if (array1[i]!=0) {
                    sb.append((char)(i+'a'));
                }
            }
            String src = sb.toString();
            for (int i = 0;i<array2.length;i++) {
                char x = (char)(i+'a');
                if (array2[i]!=0 && src.contains(x+"")) {
                    count++;
                }
            }
            System.out.println(count);

        }

    }

    //-------------------------------------------Day40-----------------------------------------------
    //No.1:发邮件
    // 这道题很简单，跟前面一道题很像。
    // 计数函数
    private static long count(long n) {
        // 这个规律可以记一下
        if (n==2) {
            return 1;
        }
        if (n==3) {
            return 2;
        }
        return (n-1)*(count(n-1)+count(n-2));
    }

    public static void main13(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            long result = count(n);
            System.out.println(result);
        }

    }

    // No.2:最长上升子序列
    // 这题也跟前面一道题很像
    // 用到了动态规划，我不太懂！！！
    public static void main(String[] args) {
        // write code here
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int x = sc.nextInt();
            int[] arr = new int[x];
            for(int i = 0;i<x;i++) {
                arr[i]=sc.nextInt();
            }
            int[] dp = new int[x];     // dp[i]表示以arr[i]结尾时的最长递增子序列长度
            Arrays.fill(dp, 1);
            int maxLen = 1;

            for(int i = 1; i < x; i++){
                for(int j = i - 1; j >= 0; j--){
                    if(arr[j] < arr[i]){
                        // arr[j] < arr[i]，可以把arr[i]接在arr[j]后面，构成长度为dp[j]+1的递增子序列
                        dp[i] = Math.max(dp[i], dp[j] + 1);     // 选择能构成更长递增子序列的arr[j]
                    }
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
            System.out.println(maxLen);
        }
    }



}

